package leetcode;

public class leetcode2016最大差值 {
	public static void main(String []args) {
		int nums[] = {7,5,5,4,3};
		System.out.println(solution1(nums));
	}
	public static int solution(int nums[]) {
		int len = nums.length;
		int ans = -1;
		for(int i=0;i < len; i++) {
			for(int j = i+1;j < len;j++) {
				if(nums[j]<nums[i] ) {
					continue;
				}
				ans = nums[j] - nums[i]>ans ?nums[j]-nums[i]:ans; 
			}
		}
		return ans;
	}
	/*
	 * 优化的点 在 哪里 以及复杂度 主要 高在什么地方 
	 * 以及怎么优化 这才是重点
	 * 这里 是 记录 一下 nums[index] 前面的最小值 
	 *  走过的路 就记录 下来 这个 方法 真的 很有用  
	 * 记忆化 搜索
	 */
	public static int solution1(int nums[]) {
//		int min = Integer.MAX_VALUE;
		int min = nums[0];
		int ans = -1;
		for(int num : nums) {
			if(num <= min) {
				min=num;//  就是小于  相等的情况 直接 不要
				continue;
			}
			ans=Math.max(num-min, ans);
		}
		return ans;
	}
}
